Elliptic curve cryptosystems (ECC) are public-key cryptosystems that have attracted increasing attention in recent years due to their shorter key length requirement in comparison with other public-key cryptosystems such as RSA.
Public-key cryptosystems make use of a pair of keys, called public and private keys, to perform cryptographic operations such as encryption/decryption of data and signing/verification of digital signatures. In particular for ECC, in some protocols private keys are scalar values that are kept in secret, and public keys are points on the elliptic curve that are made public. Given a secret scalar k and points P and kP on a elliptic curve, where kP is a multiple of the point P, the elliptic curve discrete logarithm problem (ECDLP) is defined as the problem of determining k, with P and kP known. The ECDLP problem is thought to be hard to solve, and the difficulty to solve it is precisely the security foundation of EC-based systems.
ECC can be defined over different finite fields. Most important finite fields used to date to implement this cryptosystem have been binary, prime and extension fields. Finite fields are denoted by GF(q), where q is a prime power of the form pm (p prime) and also represents the number of elements (order) of the field. If m=1, this field is referred to as prime field. If, otherwise, m≧2 then it is known as extension field. The particular case m=2 among extension fields is also known as binary field.
For the case of prime fields, the generic equation to represent an elliptic curve is given by:E: y2=x3+ax+b, where: a,bεGF(p) and Δ=4a3+27b2≠0(mod p) (Δ denotes the discriminant of the curve E).
For the case of binary fields, the generic equation to represent an elliptic curve is given by:E: y2+xy=x3+ax2+b, where: a,bεGF(2m) and Δ=b≠0.
Other variants of elliptic curve forms that also use prime, extended and/or binary fields can be found in the literature. Some examples are: Hessian and Jacobi forms, Edwards curves, Montgomery curves, elliptic curves of degree ⅔ isogenies, among others.
The central and most time-consuming operation in ECC is scalar multiplication, which is generally represented by kP. This operation can be interpreted as the result of adding the point P to itself (i.e., P+P+ . . . +P) (k−1) times, where k is a scalar of very large value. Currently, a secure ECC system uses scalars with bit lengths in the range [160,512], where larger values provide higher security level.
Another important aspect related to the deployment of a cryptosystem is its vulnerability to attacks exploiting side-channel information.
Side-channel information, such as power dissipation and electromagnetic emission, leaked by real-world devices has been shown to be highly useful for revealing private keys and effectively breaking the otherwise mathematically-strong ECC cryptosystem.
There are two main strategies to these attacks: simple (SSCA) and differential (DSCA) side-channel attacks. SSCA is based on the analysis of a single execution trace of a scalar multiplication to guess the secret key by revealing the sequence of operations used in the execution of ECC point arithmetic.
Extensive research has been carried out to yield effective countermeasures to deal with SSCA. Among them, side-channel atomicity dissolves point operations into small homogenous blocks, known as atomic blocks, which cannot be distinguished from one another through simple side-channel analysis because each one contains the same pattern of basic field operations. Furthermore, atomic blocks are made sufficiently small to make this approach inexpensive. For example the structure M-A-N-A (field multiplication, addition, negation, addition) has been proposed to build SSCA-protected point operations over prime fields.
However, the main drawback of the traditional M-A-N-A structure is that it relies on the assumption that field multiplication and squaring are indistinguishable from each other. In software implementations, timing and power consumption have been shown to be quite different for these operations, making them directly distinguishable through power analysis. Furthermore, from a performance viewpoint, the M-A-N-A structure is not optimal in several settings where the increased number of field additions that it requires becomes non-negligible.
Nowadays, embedded computers dominate the marketplace. They are used in almost every new application requiring certain computing capabilities, especially in those involving consumer devices. A very important issue involves providing adequate security to these applications. However, this task seems to contrast with the effort by manufacturers of reducing product cost, size and power consumption. It is therefore a challenging task to make possible the implementation of cryptographic systems on these constrained devices. In particular for ECC, there is a need for accelerating the scalar multiplication without impacting memory and keeping it protected against side-channel attacks, in such a way that its implementation can be realized in the myriad of new devices with limited resources.